#include "naive.h"

int32_t
run_lcs_naive(char* s1, uint32_t sz1, char* s2, uint32_t sz2, char **lcs)
{
  uint32_t i, j, n;
  int16_t **c;

  // Allocate memory for LCS memoization matrix
  c = (int16_t **) malloc(sizeof(int16_t *) * (sz1 + 1));

  if (!c) {
    fprintf(stderr, "Out of memory!\n");
    return -1;
  }

  for (i = 0; i <= sz1; i++) {
    c[i] = (int16_t *) malloc(sizeof(uint16_t) * (sz2 + 1));
    if (!c[i]) {
      fprintf(stderr, "Out of memory!\n");
      return -1;
    }
  }
  
  // Initialize memoization matrix
  for (i = 0; i <= sz1; i++) {
    c[i][0] = 0;
  }

  for (j = 0; j <= sz2; j++) {
    c[0][j] = 0;
  }

  // Start DP
  for (i = 1; i <= sz1; i++) {
    for (j = 1; j <= sz2; j++) {
      if (s1[i-1] == s2[j-1]) {
	c[i][j] = c[i-1][j-1] + 1;
      }
      else {
	c[i][j] = MAX(c[i-1][j], c[i][j-1]);
      }
    }
  }

  n = c[sz1][sz2];

  // Compute LCS
  if (lcs) {
    *lcs = (char *) malloc(sizeof(char) * n);
    if (!*lcs) {
      fprintf(stderr, "Out of memory!\n");
      return -1;
    }
    
    read_lcs(c, s1, s2, *lcs, sz1, sz2, n-1);
  }

  for (i = 0; i <= sz1; i++) {
    free(c[i]);
  } 

  free(c);

  return n;
}

void
read_lcs(int16_t** c, char* s1, char* s2, char* lcs, 
	 uint32_t i, uint32_t j, uint32_t k)
{
  if (!i || !j) return;

  if (s1[i-1] == s2[j-1]) {
    lcs[k] = s1[i-1];
    read_lcs(c, s1, s2, lcs, i-1, j-1, k-1);
  }
  else {
    if (c[i][j-1] > c[i-1][j]) {
      read_lcs(c, s1, s2, lcs, i, j-1, k);
    }
    else {
      read_lcs(c, s1, s2, lcs, i-1, j, k);
    }
  }
}
